#include <cstdio>

__int64 e[ 100001 ];
int f[ 100001 ][ 16 ], c[ 100001 ];

void init( )
{
    int i, j;
    e[ 1 ] = 1;
    for ( i = 2; i <= 100000; i++ )
    {
        if ( !e[ i ] )
            for ( j = i; j <= 100000; j += i )
            {
                if ( !e[ j ] )
                    e[ j ] = j;
                e[ j ] = e[ j ] * ( i - 1 ) / i;
                f[ j ][ c[ j ]++ ] = i;
            }
        e[ i ] += e[ i - 1 ];
    }    
}

__int64 dfs( int p, int a, int b )
{
    int i;
    __int64 ans = 0;
    for ( i = p; i < c[ b ]; i++ )
        ans += a / f[ b ][ i ] - dfs ( i + 1, a / f[ b ][ i ], b );
    return ans;
}

void work( )
{
    int i, a, b, t, k;
    __int64 ans;
    scanf("%d%d%d%d%d", &t, &a, &t, &b, &k);
    if ( a > b )
    {
        t = a;
        a = b;
        b = t;
    }
    if ( !k )
    {
        puts("0");
        return ;
    }
    a /= k;
    b /= k;
    ans = e[ a ];
    for ( i = a + 1; i <= b; i++ )
        ans += a - dfs( 0, a, i );
    printf("%I64d\n", ans);
}

int main( )
{
    int t, i;
    init( );
    scanf("%d", &t);
    for ( i = 1; i <= t; i++ )
    {
        printf("Case %d: ", i);
        work( );
    }
    return 0;
}
